Stirling number

In mathematics, Stirling numbers arise in a variety of combinatorics problems. They are named after James Stirling, who introduced them in the 18th century. Two different sets of numbers bear this name: the Stirling numbers of the first kind and the Stirling numbers of the second kind.

Contents

Notation

Several different notations for the Stirling numbers are in use. Stirling numbers of the first kind are written with a small s, and those of the second kind with a large S (Abramowitz and Stegun use an uppercase S and a blackletter S respectively). Common notations are:

s(n,k)\text{ (signed)}\,
\left[{n \atop k}\right]=c(n,k)=|s(n,k)|\text{ (unsigned)}\,
\left\{\begin{matrix} n \\ k \end{matrix}\right\}=S(n,k)= S_n^{(k)} .\,

The notation of using brackets and braces, in analogy to the binomial coefficients, was introduced in 1935 by Jovan Karamata and promoted later by Donald Knuth; it is referred to as Karamata notation. (The bracket notation conflicts with a common notation for the Gaussian coefficients.) The mathematical motivation for this type of notation, as well as additional Stirling number formulae, may be found on the page for Stirling numbers and exponential generating functions.

Stirling numbers of the first kind

Main article: Stirling numbers of the first kind

Unsigned Stirling numbers of the first kind

c(n,k)=\left[{n \atop k}\right]=|s(n,k)|=(-1)^{n-k} s(n,k)

(with a lower-case "s") count the number of permutations of n elements with k disjoint cycles.

Stirling numbers of the first kind (without the qualifying adjective unsigned) are the coefficients in the expansion

(x)_{n} = \sum_{k=0}^n s(n,k) x^k.

where (x)_{n} is the Pochhammer symbol for the falling factorial,

(x)_{n}=x(x-1)(x-2)\cdots(x-n%2B1).

Note that (x)0 = 1 because it is an empty product. Combinatorialists also sometimes use the notation x^{\underline{n\!}} for the falling factorial, and x^{\overline{n\!}} for the rising factorial.[1]

(Confusingly, the Pochhammer symbol that many use for falling factorials is used in special functions for rising factorials.)

Stirling numbers of the second kind

Main article: Stirling numbers of the second kind

Stirling numbers of the second kind count the number of ways to partition a set of n elements into k nonempty subsets. They are denoted by S(n,k) or \textstyle \lbrace{n\atop k}\rbrace.[2] The sum

\sum_{k=0}^n \left\{\begin{matrix} n \\ k \end{matrix}\right\} = B_n

is the nth Bell number. Using falling factorials, we can also characterize the Stirling numbers of the second kind by

\sum_{k=0}^n \left\{\begin{matrix} n \\ k \end{matrix}\right\}(x)_k=x^n.

The Lah number, are sometimes being referred as Stirling numbers of the third kind. for example see.

Inversion relationships

The Stirling numbers of the first and second kind can be considered to be inverses of one another:

\sum_{n=0}^{\max\{j,k\}} (-1)^{n-k} \left[{n\atop j}\right] \left\{{k\atop n}\right\} = \delta_{jk}

and

\sum_{n=0}^{\max\{j,k\}} (-1)^{n-k} \left\{{n\atop j}\right\} \left[{k\atop n}\right] = \delta_{jk}

where \delta_{jk} is the Kronecker delta. These two relationships may be understood to be matrix inverses. That is, let s be the lower triangular matrix of Stirling numbers of first kind, so that it has matrix elements

[s]_{nk}=s(n,k)=(-1)^{n-k} \left[{n\atop k}\right].\,

Then, the inverse of this matrix is S, the lower triangular matrix of Stirling numbers of second kind. Symbolically, one writes

s^{-1} = S\,

where the matrix elements of S are

[S]_{nk}=S(n,k)=\left\{{n\atop k}\right\}.

Note that although s and S are infinite, this works for finite matrices by only considering Stirling numbers up to some number N.

A generalization of the inversion relationship gives the link with Lah numbers L(n,k)

(-1)^n L(n,k) = \sum_{z}(-1)^{z} s(n,z)\left\{{z\atop k}\right\},

with the conventions L(0,0)=1 and L(n , k )=0 if k>n.

Symmetric formulae

Abramowitz and Stegun give the following symmetric formulae that relate the Stirling numbers of the first and second kind.

\left[{n\atop k}\right] = (-1)^{n-k} \sum_{j=0}^{n-k} (-1)^j {n-1%2Bj \choose n-k%2Bj} {2n-k \choose n-k-j} \left\{{n-k%2Bj\atop j}\right\}

and

\left\{{n\atop k}\right\} = (-1)^{n-k} \sum_{j=0}^{n-k} (-1)^j {n-1%2Bj \choose n-k%2Bj} {2n-k \choose n-k-j} \left[{n-k%2Bj\atop j}\right].

See also

References

  1. ^ Aigner, Martin (2007). "Section 1.2 - Subsets and Binomial Coefficients". A Course In Enumeration. Springer. pp. 561. ISBN 3540390324. 
  2. ^ Ronald L. Graham, Donald E. Knuth, Oren Patashnik (1988) Concrete Mathematics, Addison-Wesley, Reading MA. ISBN 0-201-14236-8, p. 244.